home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 029a / pdsrt321.zip / PDQSORT.C < prev    next >
C/C++ Source or Header  |  1991-02-05  |  7KB  |  171 lines
  1. /*****************************************************************************
  2. *  pdqsort.c -- A public domain implementation of an iterative version of    *
  3. *  the QuickSort algorithm with "Median of Three" pivot selection,           *
  4. *  "end recursion removal", and the use of an Insertion Sort for small       *
  5. *  partitions.  Many people have "improved" C. A. R. Hoare's original        *
  6. *  QuickSort algorithm.  This implementation follows Robert Sedgewick's      *
  7. *  ("Algorithms in C", Robert Sedgewick, Addison-Wesley, 1990,               *
  8. *  ISBN 0-201-51425-7) improvements.                                         *
  9. *                                                                            *
  10. *  An interative qsort() is faster and requires less stack space than the    *
  11. *  recursive implementation.  If "end recursion removal" is employed, the    *
  12. *  maximum number of stack entries required will be no more than log to the  *
  13. *  base 2 of the number of elements in the array being sorted.               *
  14. *                                                                            *
  15. *  Sedgewick states that the use of an Insertion Sort for partitions smaller *
  16. *  than M elements, where M is a constant between 5 and 25, results in       *
  17. *  about a 20% improvement in the efficiency of the sort.                    *
  18. *****************************************************************************/
  19.  
  20. #include <stdlib.h>
  21.  
  22. static void     Swap(void *a, void *b);
  23.  
  24. static unsigned IntCount, ByteCount;        /* Used in the Swap() routine    */
  25.  
  26. int             M = 8;                        /* The threshold for Insertion    */
  27.  
  28. /*****************************************************************************
  29. *  The main qsort() routine.  This implementation is fully compatible with   *
  30. *  the standard qsort() routine in the ANSI C run time libraries.            *
  31. *                                                                            *
  32. *  base is the base address of the array to be sorted, nelem is the number of*
  33. *  entries in the array to be sorted, width is the width of a single element *
  34. *  in bytes, and fcmp is a pointer to a function that performs the comparison*
  35. *  between elements of the array.                                            *
  36. *                                                                            *
  37. *  The pointer L scans partitions from the Left, the pointer R scans         *
  38. *  partitions from the right, Limit is a pointer that serves as a sentinel   *
  39. *  to stop the scan on the right (the pivot element is stored at base and    *
  40. *  serves as the left end sentinel).  InsertThresh is the M constant         *
  41. *  converted to a pointer for comparisons.                                   *
  42. *****************************************************************************/
  43.  void
  44. qsort (void *base, size_t nelem, size_t width,
  45.        int (*fcmp) (const void *a, const void *b)) {
  46.     char           *L, *R, *Limit;
  47.     unsigned        InsertThresh;
  48.  
  49. /***************************************************************************
  50. *  The stack used to push the bounds of the larger partition.  Thirty-two  *
  51. *  entries will allow for sorting an array with a little over 4 million    *
  52. *  entries!                                                                *
  53. ***************************************************************************/
  54.     struct {
  55.         char           *Base;
  56.         char           *Limit;
  57.         }               Stack[32], *Sptr;
  58.  
  59.     /* Initialization    */
  60.  
  61.     IntCount = width / sizeof(int);
  62.     ByteCount = width % sizeof(int);
  63.     InsertThresh = M * width;
  64.     Sptr = Stack;
  65.     Limit = (char *) base + nelem * width;
  66.  
  67.     while (1) {
  68.         while (Limit - base > InsertThresh) {
  69.             L = (char *) base + width;
  70.             R = Limit - width;
  71.  
  72. /**************************************************************************
  73. *  The following code implements Sedgewick's "Median of Three" selection  *
  74. *  for the pivot element.  The central element is selected as the first   *
  75. *  tentative pivot                                                        *
  76. **************************************************************************/
  77.  
  78.             Swap(((unsigned) (Limit - base) >> 1)
  79.                  - ((((unsigned) (Limit - (char *) base) >> 1)) % width)
  80.                  + (char *) base, base);
  81.             if ((*fcmp) (L, R) > 0) Swap(L, R);
  82.             if ((*fcmp) (base, R) > 0) Swap(base, R);
  83.             if ((*fcmp) (L, base) > 0) Swap(L, base);
  84.  
  85.     /*************************************************
  86.     *  The following code performs the partitioning  *
  87.     *************************************************/
  88.  
  89.             while (1) {
  90.                 while ((*fcmp) ((L += width), base) < 0);
  91.                 while ((*fcmp) ((R -= width), base) > 0);
  92.                 if (L > R) break;
  93.                 Swap(L, R);
  94.                 }
  95.             Swap(base, R);
  96.  
  97.  /**************************************************************************
  98.  *  The following code performs the "end recursion removal".  This is      *
  99.  *  accomplished by stacking the larger partition and immediately sorting  *
  100.  *  the smaller.                                                           *
  101.  **************************************************************************/
  102.  
  103.             if (R - base > Limit - L) {
  104.                 Sptr->Base = base;
  105.                 Sptr->Limit = R;
  106.                 base = L;
  107.                 }
  108.             else {
  109.                 Sptr->Base = L;
  110.                 Sptr->Limit = Limit;
  111.                 Limit = R;
  112.                 }
  113.             Sptr++;
  114.             }
  115.  
  116. /*****************************************************************************
  117. *  The following code is the Insertion Sort used to sort partitions smaller  *
  118. *  the M elements.                                                           *
  119. *****************************************************************************/
  120.  
  121.         L = (char *) base + width;
  122.         while (L < Limit) {
  123.             R = L;
  124.             while (R > base && (*fcmp) (R - width, R) > 0) {
  125.                 Swap(R - width, R);
  126.                 R -= width;
  127.                 }
  128.             L += width;
  129.             }
  130. /****************************************************************************
  131. *  If there are any partitions left on the stack, pop one off and sort it.  *
  132. *  Otherwise, the qsort is finished.                                        *
  133. ****************************************************************************/
  134.  
  135.         if (Sptr > Stack) {
  136.             --Sptr;
  137.             base = Sptr->Base;
  138.             Limit = Sptr->Limit;
  139.             }
  140.         else break;
  141.         }
  142.     }
  143.  
  144. /****************************************************************************
  145. *  Swap() -- The routine used by the main qsort() routine to swap elements  *
  146. *  of the array when necessary.  To save time, Swap() will swap in integer  *
  147. *  units until there is less than a full integer left.  Then it will swap   *
  148. *  in byte units until the entire element has been swapped.                 *
  149. ****************************************************************************/
  150.  
  151.  static void
  152. Swap (void *a, void *b) {
  153.     unsigned        tmp;
  154.     unsigned        i;
  155.  
  156.  
  157.     for (i = 0; i < IntCount; i++) {
  158.         tmp = *((unsigned *) a);
  159.         *((unsigned *) a) = *((unsigned *) b);
  160.         *((unsigned *) b) = tmp;
  161.         ((unsigned *) a)++;
  162.         ((unsigned *) b)++;
  163.         }
  164.     for (i = 0; i < ByteCount; i++) {
  165.         tmp = *((unsigned char *) a);
  166.         *((unsigned char *) a) = *((unsigned char *) b);
  167.         *((unsigned char *) b) = tmp;
  168.         ((unsigned char *) a)++;
  169.         ((unsigned char *) b)++;
  170.         }
  171.     }